package com.kristin.sort;

/**
 * 插入排序的改进版本，缩小增量排序
 */
public class ShellSort {

    public void sort(int[] arrs) {
        int gap = arrs.length /2 ;
        while(gap >0){
            sort(arrs, gap);
            gap--;
        }
    }

    public void sort(int[] arrs, int gap) {
        for(int i = gap ; i< arrs.length ; i++ ) {
            int current = arrs[i];
            int preIndex = i - gap;
            while(preIndex >= 0 && arrs[preIndex] > current) {
                arrs[preIndex + gap] = arrs[preIndex];
                preIndex = preIndex - gap;
            }
            arrs[preIndex + gap] = current;
        }
    }


    public static void main(String[] args) {
        int[] arrs = new int[]{10, 9, 8, 7, 4, 3, 2, 1, 6, 5};
        new ShellSort().sort(arrs);
        print(arrs);
    }

    public static void print(int[] arrs) {
        for (int i : arrs) {
            System.out.print(i + "\t");
        }
    }

}
